#include <iostream>
#include <queue>
#include <string>
#include <cstdlib>
#include <ctime>
#include <sstream>
#include <algorithm>

using namespace std;

// 节点结构定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right)
        : val(x), left(left), right(right) {}
};

// 1. 随机生成二叉树（控制最大节点数）
TreeNode* generateRandomTree(int maxNodes) {
    if (maxNodes <= 0) return nullptr;
    srand(time(0) + rand()); // 增加随机性
    
    // 随机决定当前节点是否生成（根节点必生成）
    TreeNode* root = new TreeNode(rand() % 100); // 节点值范围[0,99]
    int remaining = maxNodes - 1; // 剩余可分配节点数
    
    if (remaining == 0) return root;
    
    // 随机分配左子树节点数（0 ~ remaining）
    int leftNodes = rand() % (remaining + 1);
    int rightNodes = remaining - leftNodes;
    
    // 递归生成左右子树
    root->left = generateRandomTree(leftNodes);
    root->right = generateRandomTree(rightNodes);
    
    return root;
}

// 2. 层序序列化二叉树（用于打印和比较结构）
// 格式：空节点用"#"表示，节点间用","分隔（例如：1,2,3,#,#,4,#,#,#）
string serialize(TreeNode* root) {
    if (!root) return "#";
    string res;
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        
        if (cur) {
            res += to_string(cur->val) + ",";
            q.push(cur->left);  // 即使为空也入队，保证结构完整
            q.push(cur->right);
        } else {
            res += "#,";
        }
    }
    
    // 去除末尾多余的","
    if (!res.empty()) res.pop_back();
    return res;
}

// 3. 复制二叉树（避免原树被修改影响对比）
TreeNode* copyTree(TreeNode* root) {
    if (!root) return nullptr;
    TreeNode* newNode = new TreeNode(root->val);
    newNode->left = copyTree(root->left);
    newNode->right = copyTree(root->right);
    return newNode;
}

// 4. 销毁二叉树（释放内存）
void destroyTree(TreeNode* root) {
    if (!root) return;
    destroyTree(root->left);
    destroyTree(root->right);
    delete root;
}

// 5. 基准算法（以"判断完全二叉树"为例，已知正确的实现）
// 完全二叉树定义：层序遍历中，出现空节点后不能再有非空节点
bool isCompleteTreeStandard(TreeNode* root) {
    if (!root) return true; // 空树是完全二叉树
    queue<TreeNode*> q;
    q.push(root);
    bool hasNull = false; // 标记是否已出现空节点
    
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        
        if (!cur) {
            hasNull = true;
        } else {
            if (hasNull) return false; // 空节点后出现非空节点，非完全二叉树
            q.push(cur->left);
            q.push(cur->right);
        }
    }
    return true;
}

struct comp 
{
	bool iscomplete;
	int small;
	int big;
	comp():iscomplete(false),small(-1),big(-1){}
};

comp proc(TreeNode* Node)
{
	if(Node == nullptr)
	{
		comp a;
		a.iscomplete = true;
		a.big = 0;
		a.small = 0;
		return a;
	}
	comp c1 = proc(Node->left);
	comp c2 = proc(Node->right);
	comp c;
	if(c1.iscomplete == false || c2.iscomplete == false) {
		c.iscomplete = false;
	}
	else if((c1.small - c2.big != 1)) {
		c.iscomplete = true;
	}
	else if(c1.big - c2.small != 1)
	{
		c.iscomplete = false;
	}
	else {
	 	c.iscomplete = true;
	}
	c.small = std::min(c1.small,c2.small) + 1;
	c.big = std::max(c1.big,c2.big) + 1;
	return c;
}

// 6. 待测试算法（用户需在此实现自己的逻辑）
// 示例：假设这是用户编写的判断完全二叉树的函数（可能正确或错误）
bool isCompleteTreeTest(TreeNode* root) {
	return proc(root).iscomplete;
}

// 7. 对数器主函数：循环测试并验证算法正确性
void testAlgorithm(int testTimes, int maxNodes) {
    srand(time(0));
    for (int i = 0; i < testTimes; ++i) {
        // 生成随机树
        TreeNode* root = generateRandomTree(rand() % (maxNodes + 1));
        // 复制树（避免测试函数修改原树）
        TreeNode* rootCopy = copyTree(root);
        
        // 用两种方法判断
        bool standardRes = isCompleteTreeStandard(root);
        bool testRes = isCompleteTreeTest(rootCopy);
        
        // 结果不一致时输出错误信息
        if (standardRes != testRes) {
            cout << "测试失败！" << endl;
            cout << "树结构（序列化）：" << serialize(root) << endl;
            cout << "基准算法结果：" << (standardRes ? "是完全二叉树" : "不是完全二叉树") << endl;
            cout << "待测试算法结果：" << (testRes ? "是完全二叉树" : "不是完全二叉树") << endl;
            // 释放内存
            destroyTree(root);
            destroyTree(rootCopy);
            return;
        }
        
        // 释放内存
        destroyTree(root);
        destroyTree(rootCopy);
    }
    cout << "所有测试通过！共测试" << testTimes << "次" << endl;
}

vector<string> split(const string &s, char delimiter) {
    vector<string> tokens;
    string token;
    istringstream tokenStream(s);
    while (getline(tokenStream, token, delimiter)) {
        tokens.push_back(token);
    }
    return tokens;
}

TreeNode* deserialize(const string &data) {
    if (data.empty() || data == "#") return nullptr; // 空树处理
    
    vector<string> nodes = split(data, ','); // 分割字符串为节点列表
    int index = 0; // 用于遍历节点列表
    
    // 创建根节点（第一个节点必为非空）
    TreeNode* root = new TreeNode(stoi(nodes[index++]));
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty() && index < nodes.size()) {
        TreeNode* current = q.front();
        q.pop();
        
        // 处理左孩子
        if (nodes[index] != "#") {
            current->left = new TreeNode(stoi(nodes[index]));
            q.push(current->left); // 左孩子入队，后续处理它的子节点
        }
        index++; // 无论左孩子是否为空，索引都后移
        
        // 处理右孩子（需确保索引未越界）
        if (index < nodes.size()) {
            if (nodes[index] != "#") {
                current->right = new TreeNode(stoi(nodes[index]));
                q.push(current->right); // 右孩子入队
            }
            index++;
        }
    }
    
    return root;
}


int main() {
    // 测试参数：测试10000次，最大节点数为20
    //testAlgorithm(100, 5);
    string a = "58,47,#,29,#,#,#";
    TreeNode* p = deserialize(a);
    cout<<isCompleteTreeTest(p);
    return 0;
}

